package com.ky.leetcode.剑指Offer;

/*

在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

    示例:
    现有矩阵 matrix 如下：
    [
        [1,   4,  7, 11, 15],
        [2,   5,  8, 12, 19],
        [3,   6,  9, 16, 22],
        [10, 13, 14, 17, 24],
        [18, 21, 23, 26, 30]
    ]
    给定 target = 5，返回 true。
    给定 target = 20，返回 false。

    限制：
    0 <= n <= 1000
    0 <= m <= 1000

 */

public class 剑指Offer04二维数组中的查找 {
    public static void main(String[] args) {
        int[][] matrix = new int[][]{
                {5}};
        System.out.println(new Solution().findNumberIn2DArray(matrix, 5));
    }

    static class Solution {
        public boolean findNumberIn2DArray(int[][] matrix, int target) {
            boolean result = false;
            for (int i = 0; i < matrix.length; i++) {
                result = findNumberInArray(matrix[i], target);
                if (result)
                    break;
            }
            return result;
        }

        public boolean findNumberInArray(int[] matrix, int target) {
            int lo = 0, hi = matrix.length - 1;
            while (lo <= hi) {
                int mid = lo + (hi - lo) / 2;
                if (target == matrix[mid]) return true;
                else if (target < matrix[mid]) hi = mid - 1;
                else if (target > matrix[mid]) lo = mid + 1;
            }
            return false;
        }

    }
}
